#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
typedef int DataType;

// 要求将所有代码写在本文件内
typedef struct Node
{
    DataType data;
    struct Node *next;
}SLNode;
/*单链表初始化。初始化成功函数返回0，否则返回1。*/
int ListInitiate(SLNode **head){
    *head = (SLNode *)malloc(sizeof(SLNode));  //为头结点申请内存空间
    if( *head == NULL){
        printf("初始化失败！\n");
        return 1;
    }
    (*head)->next = NULL;  //头结点下一指针是NULL，即完成初始化
    return 0;  //失败返回0
}

/* 函数返回由head所表示的单链表的长度。*/
int ListLength(SLNode *head){
    SLNode *p; //定义一个指针变量p
    int lengh = 0; //初始化长度length为0
    p = head->next;  //p指向第一个结点
    while (p != NULL){  //遍历单链表 在p不为NULL的时候
        lengh ++;  //长度length++
        p = p->next;
    }
    return lengh;  //返回（长度）length
}

int ListInsert(SLNode *head, int i, DataType x){
    SLNode *p;  //创建一个指针p，p可以指向任何一个元素
    p = head;  //将单链表的头结点指针赋值给p
    int j = 0;  //设一个新的变量j，从第一个结点开始查找插入的位置
    while (p->next != NULL && j < i){
        /*因为单链表没有下标，所以必须，一个一个的查找
        当j < i时，说明还没有到i所插入的那个位置*/
        p = p -> next;   //因为没到，所以将头指针的下一个指针位置赋值给p
        j ++;  //往后移动一位
    }
    SLNode *s;  //定义插入的结点
    s  = (SLNode *)malloc(sizeof(SLNode));  //给新的结点分配内存空间，加强制类型转换
    if(s){
        s->data = x;  
        s->next = p->next;  
        p->next = s; 
        return 1;  //插入成功返回1
    }
    return 0;  //插入失败返回0
}


// 在由head所表示的单链表里删除位置 i 上的元素并将其值存入 x 变量里。调用成功后，列表长度减1。
int ListDelete(SLNode *head, int i, DataType *x){
    int k = 0; //定义新的变量k为0，从第一个结点开始查找i位置
    SLNode *p,*q;  //定义两个指针变量
    p = head;  //将单链表的头结点指针赋值给p
    while(p != NULL && k < i){  //同插入的时候一样，是查找i的位置
        p = p->next;
        k ++;
    }
    if(p == NULL){
        printf("删除位置不合法！\n");
        return 0;
    }
    q = p->next; //找到i所在的位置，将它所在的指针地址，赋值给q
    *x = q->data;
    p->next = q->next;   //将它所指向的下一个结点的
    free(q); //free函数释放已删除结点的内存
    return 1;
}


int ListGet(SLNode *head, int i, DataType *x){
    SLNode *p = head;  //定义一个指针变量
    int j = -1;  //定义一个int类型的 变量j  并赋值为1，从第一个结点开始查找

    while(p != NULL && j < i){  //同插入的时候一样，是查找i的位置
        p = p->next;
        j ++;
    }

    if(p == NULL || j > i){  //如果满足其中任意一个条件，则说明i的位置的值不对。没有这个结点
        printf("%d个结点不存在\n",i);
        return 0;
    }else{
        *x = p->data;
        return 1;
    }
}

int Destroy(SLNode **head){
    SLNode *p,*q;  //定义两个指针变量
    p = (*head)->next;  //将第一个结点的地址赋值给p指针变量
    while (p != NULL){
        q = p->next;   //将下一个结点的内存赋值给p指针变量
        free(p);   //释放结点的内存
        p = q;   // 重新开始，将q中保存的下一个结点的内存地址赋值给p

    }
    (*head) = NULL;  
    return *head ? 1 : 0;
}

//遍历单链表
void ErgodicLinkedList(SLNode *head){
    SLNode *p; //定义一个指针变量p
    for (p = head->next; p != NULL; p = p->next){
//        p先等于头结点指针的下一个地址，就是第一个结点的地址
//        判断p是否为NULL，就是是否已经到了最后一个结点
//        然后，将下一个结点的地址赋值给p，就是一次往后查找。
        printf("%3d",p->data);   //利用指针输出结点的元素
    }
}

void main(void) {
    SLNode *head;
    int i , x;
    ListInitiate(&head);/*初始化*/
    for(i = 0; i < 10; i++) {
        if(ListInsert(head, i, i+1) == 0) /*插入10个数据元素*/
        {
            printf("错误! \n");
            return;
        }
    }

    if(ListDelete(head, 4, &x) == 0) { /*删除数据元素5*/
        printf("错误! \n");
        return;
    } else{
        printf("删除的元素为:%d\n",x);
    }

    printf("%d\n", ListLength(head));

    for(i = 0; i < ListLength(head); i++) {
        if(ListGet(head, i, &x) == 0) /*取元素*/
        {
            printf("错误! \n");
            return;
        }
        else printf("%d    ", x);/*显示数据元素*/
    }

    int num = Destroy(&head);
    printf("是否销毁%d\n",num);

    for(i = 0; i < ListLength(head); i++) {
        if(ListGet(head, i, &x) == 0) /*取元素*/
        {
            printf("错误! \n");
            return;
        }
        else printf("%d    ", x);/*显示数据元素*/
    }


}